package com.cf.r1017_ak;

import java.io.*;
import java.util.*;

public class h {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

        in.nextToken();
        int T = (int) in.nval;
        while (T-- > 0) {
            in.nextToken();
            int n = (int) in.nval;
            in.nextToken();
            int q = (int) in.nval;

            int[] a = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                in.nextToken();
                a[i] = (int) in.nval;
            }

            // 构建 pos：值 -> 出现该值的所有下标（升序）
            Map<Integer, ArrayList<Integer>> pos = new HashMap<>();
            for (int i = 1; i <= n; i++) {
                pos.computeIfAbsent(a[i], k -> new ArrayList<>()).add(i);
            }

            // 处理每个查询
            while (q-- > 0) {
                in.nextToken();
                int k = (int) in.nval;
                in.nextToken();
                int l = (int) in.nval;
                in.nextToken();
                int r = (int) in.nval;

                long ans = 0;
                int curK = k;
                int curPos = l;

                // 主循环：只在 curK > 1 且区间未走完时处理“跳跃”
                while (curPos <= r && curK > 1) {
                    // 枚举 curK 的所有因子（≥2）
                    ArrayList<Integer> divs = new ArrayList<>();
                    int sq = (int) Math.sqrt(curK);
                    for (int d = 2; d <= sq; d++) {
                        if (curK % d == 0) {
                            divs.add(d);
                            if (d != curK / d) divs.add(curK / d);
                        }
                    }
                    if (curK > 1) divs.add(curK);

                    // 在所有能整除 curK 的 a[i] 位置中找最小下标
                    int nextPos = Integer.MAX_VALUE;
                    for (int d : divs) {
                        ArrayList<Integer> lst = pos.get(d);
                        if (lst == null) continue;
                        int idx = Collections.binarySearch(lst, curPos);
                        if (idx < 0) idx = -idx - 1;
                        if (idx < lst.size()) {
                            nextPos = Math.min(nextPos, lst.get(idx));
                        }
                    }
                    if (nextPos > r || nextPos == Integer.MAX_VALUE) break;

                    // [curPos, nextPos) 上 curK 不变
                    ans += 1L * curK * (nextPos - curPos);

                    // 在 nextPos 位置做整除跳跃
                    int x = a[nextPos];
                    while (curK % x == 0) {
                        curK /= x;
                    }
                    ans += curK;
                    curPos = nextPos + 1;
                }

                // 若还有剩余区间，curK 不再变化，直接批量加
                if (curPos <= r) {
                    ans += 1L * curK * (r - curPos + 1);
                }

                out.println(ans);
            }
        }
        out.flush();
    }
}
